// https://leetcode.cn/problems/powx-n/

// 法一：递归
class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) return 1.0;
        double y = quickMul(x, N / 2);
        return N % 2 == 0? y * y: y * y * x;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N > 0? quickMul(x, N): 1.0 / quickMul(x, -N);
    }
};

// 法二：迭代
class Solution {
public:
// 从x开始不断平方，得到x^2, x^4, x^8... 如果n从右往左第k位（从0开始）二进制是1，就将对应的x^(2^k)计入答案。
    double quickMul(double x, long long N) {
        double ans = 1.0;
        double x_contri = x;
        while (N) {
            if (N % 2 == 1) ans *= x_contri;
            x_contri *= x_contri;
            N >>= 1;
        }
        return ans;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N > 0? quickMul(x, N): 1.0 / quickMul(x, -N);
    }
};